Linear filters implemented with digital signal processing, generally with constant coefficients, are widely used in electronic systems, particularly in systems configured with digital logic. For example, digital filters are widely used in high fidelity audio systems, cellular telephones, speakerphones, high performance television and radio receivers, speech recognition, and numerous other applications requiring linear processing of a band-limited signal.
Digital interpolation filters are generally included in system designs to increase a signal sampling rate before a digital-to-analog (D/A) conversion process. The Nyquist rate, as is well understood in the art, is the minimum sampling rate for a band-limited signal without losing its information content. However, upsampling (“interpolating”) a band-limited signal to rates beyond the Nyquist rate allows D/A conversions with fewer bits of precision than are used for the original signal while preserving the original signal's information content. Reducing the number of bits in D/A converters often results in substantial cost reduction for a D/A device and increased conversion speed. Thus, generating oversampled signals is a frequent design approach in high performance systems such as high performance audio reproduction systems.
To achieve high filtering performance such as a flat pass band, a flat stop band, and a steep inter-band transition, high order filters are required. For example, the number of filter delay taps required to implement an FIR filter with a pass-band ripple of ±r1 centered around unity, a stop-band ripple of ±r 2 centered around zero, a transition bandwidth of Ftransition Hz, and a sampling frequency of Fsampling Hz is approximately, as described in R. A. Haddad, et al., “Digital Signal Processing: Theory, Applications and Hardware,” W.H. Freeman and Co., 1991, p. 199
                                          -            10                    ·                                    log              10                        ⁡                          (                                                r                  1                                ·                                  r                  2                                            )                                      -        13                    14.6        ·                              F            transition                                F            sampling                                +    1    ,which demonstrates the rapid growth of the number of taps necessary to implement a filter as its transition bandwidth is reduced. Thus, high performance digital filters with more than 50 or 100 taps are not uncommon for known filters with narrow transition bandwidths.
Filters configured with many taps inherently require that a significant number of digital operations be performed at a high repetition rate. This, in turn, requires that substantial chip area must be dedicated when a high-order filter is implemented with an integrated circuit, or else a high performance digital signal processor must be designed into the end product. Either of these alternatives can result in recognizable cost and power increases in the end product, and, for portable systems, a reduction in battery life.
Digital filters are usually implemented with finite-duration impulse response (FIR) filters, so named because an input signal with a limited time duration produces an output signal with a limited time duration. FIR filters, unlike infinite-duration impulse response (IIR) filters, do not exhibit stability problems because their non-recursive structure produces an output signal that only depends on ordinary numerical operations on an input signal, and with limited time delays. FIR filters have no corresponding lumped-parameter analog equivalent. FIR filters are less dependant on numerical quantization and, unlike IIR filters, can be easily designed without substantial phase error that would otherwise contribute to waveform distortion of the output signal. FIR filters are often easier to design than IIR filters because their coefficients are precisely their impulse responses. But a high performance FIR filter, like a corresponding IIR filter, bears a system cost for substantial numerical computation, particularly for multiplication of the input signal by a filter coefficient for each of the many filter taps, making a recognizable contribution to the cost of the end product.
A broad research effort has been made over the past decades to reduce the necessary computation for digital filters, particularly for high-order FIR and IIR filters, and has produced several significant results. An article by J. O. Coleman, et al., “Fractions in the Canonical-Signed Digit Number System,” 2001 Conf. on Information Sciences and Systems, Mar. 21, 2001, pp. 1-2, which is referenced and incorporated herein, describes the use of canonical signed digits (CSD) for the representation of binary numbers. Using a CSD representation recognizes and takes advantage of the fact that subtraction is no more complex than addition in binary arithmetic and both are much simpler than multiplication which is generally implemented with a series of resource-consuming shifts and adds corresponding to the number of “1” bits in the multiplier.
Other prior research efforts have produced further simplifications to the computation necessary to support FIR and IIR filters and include:                using FIR filters with symmetrical (or anti-symmetrical) impulse response that inherently maintain linear phase delay in the output signal. Such filters can be implemented with half as many multiplications as a non-symmetrical filter.        using “half-band filters,” which are FIR filters that have transforms that are even functions of frequency and which have odd symmetry about a half-bandwidth point, which produce both a symmetric impulse time response as well as zero impulse time response for the even-numbered time steps, obviating the need to calculate the response at the even-numbered points.        structuring decimation and interpolation filters as a series of cascaded stages, with each stage operating with smaller steps of decimation or interpolation, and configuring the more rapidly executed steps with lower order sub-filters. (Decimation and interpolation filters are digital filters that reduce or increase the number of sample points of an input signal by a factor of M, and typically constrain M to be 2n where n is an integer exponent.)        using efficient digital structures such as tree adders, Homer's nested multiplication, etc., and general custom logic to perform arithmetic operations in minimal time.        
Despite these advances in digital filter implementations, a remaining obstacle to low cost filter design, particularly for interpolation filters, is the need to include a dual-port FIFO (“first in/first out”) memory to supply the output data in a real-time application of a filter configured as a sequence of simpler, cascaded sub-filters, where each sub-filter operates on the output of the previous filter, and each sub-filter operates at a different repetition rate. The need for FIFO memory arises in systems configured to use a selectable upsampling rate because the timing for availability of delayed and filtered samples in the digital computation depends on the selected upsampling rate, and leads to impractical or essentially unworkable circuit or software logical structures in these flexible arrangements, or else to designs that are not cost effective for the marketplace. A dual-port FIFO memory in prior-art designs provides the interface between an ALU (arithmetic and logic unit) that performs the actual filter calculation for the cascaded sub-filters operating at the different repetition rates and the digital logic (the “glue” logic) that outputs the selected filtered samples from the cascaded sub-filters in the right order, and at the right time. Dual-port FIFO memories are a significant cost element in digital filter designs, particularly for high-order filters, usually requiring substantial die area for their implementation. A dual-port FIFO memory often consumes as much as 30% of the die area for a custom chip that can perform flexible upsampling, for example, a device that can selectively execute multiple upsampling rates for high performance, multi-channel audio applications. The additional area for a FIFO memory is important because systems may be configured with six or more independent audio channels, each requiring a separate interpolation filter. A significant contributor to the substantial die area required by filters with FIFO memory is the need for extensive interconnections between portions of the operative filter logic that are inherently separated on the die. FIFO memory macros also require special power and ground structures around them, adding to the real estate on the die. For custom filters that operate at only one upsampling rate such as sample rate doubling, extensive logical design can sometimes be included in the device to avoid the FIFO memory problem. But a majority of designs that can accommodate flexible upsampling rates have not avoided this problem.
Thus, the prior art approach uses a digital interpolation filter to produce a filtered output signal at a higher sampling rate than the sampling rate of an input signal, and a known simplification of a digital interpolation filter uses a cascade arrangement of simpler interpolation sub-filters that each perform a smaller interpolation step, such as 2:1 interpolation, for a larger step of interpolation, such as 8:1 interpolation. The first cascaded interpolation sub-filter of the prior art operates on the input sampled data sequence and produces a filtered signal at twice the input signal sampling rate. The first cascaded interpolation sub-filter is followed by a second cascaded interpolation sub-filter that operates on the interpolated signal produced by the first interpolation sub-filter and produces a filtered signal at four times the sampling rate. The second cascaded interpolation sub-filter is followed, in turn, by a third cascaded interpolation sub-filter that produces a signal at eight times the sampling rate, etc. Thus, the first cascaded interpolation sub-filter operates on the input signal and produces an interpolated signal at a higher sampling rate, followed by a second interpolation sub-filter that operates on the interpolated signal and produces a further interpolated signal at a yet higher sampling rate, etc., which makes each succeeding filtering stage dependent on the previous filtering stage, and determines the necessary order in which each stage must be executed. In addition, the entire computation must be completed before the first filtered output signal is required, i.e., at the highest repetition rate. The prior art may also use CSD and other digital efficiencies to reduce the computational load for a digital filter. To accommodate a flexible over-sampling rate for the filtered output signal, the prior art necessarily uses a dual-port FIFO memory with its attendant cost in device area to provide the output signal samples in the correct sequence and with the correct timing.
A need thus exists for a filter design that can eliminate the dual-port FIFO memory for filters configured with cascaded sub-filtering stages. Digital interpolation and decimation filter implementations such as FIR filter implementations configured with cascaded stages, particularly in systems requiring removal of spectral components that produce aliasing after interpolation or decimation of an input sampled signal, can benefit from designs that do not have need for a dual-port FIFO memory.